#include<stdio.h>

void MergeArr(int *a,int begin1,int end1,int begin2,int end2,int *tmp)
{
	int left = begin1, right = end2;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
		tmp[index++] = a[begin1++];

	while (begin2 <= end2)
		tmp[index++] = a[begin2++];

	//把归并好的再tmp的数据拷贝回原数组
	for (int i = left; i <= right; ++i)
	{
		a[i] = tmp[i];
	}
}


void MergeSortNonR(int* a, int n, int* tmp)
{
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//控制[i,i+gap-1]  [i+gap,i+2*gap-1];
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//1.合并的时候只有第一组，第二组一个数据都没有(就不需要合并)
			if (begin2>=n)
			{
				break;
			}

			//2.合并的时候第二组只有部分数据，需要修改end2边界
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			MergeArr(a, begin1, end1, begin2, end2, tmp); 
		}
		gap *= 2;
	}
}



int main()
{
	int a[] = {1,2,3,4,5,4,5,6,7};
	int tmp[] = {1,2,3,4,5,4,5,6,7};
	MergeSortNonR(a, 9, tmp);
	for(int i = 0;i<9;++i)
	{
		printf("%d ", a[i]);
	}
}
